package com.example.demo.arithmetic.datastructure.stack;

import java.util.LinkedList;

// 中缀表达式转后缀表达式
public class InfixToSuffix {

    public static void main(String[] args) {
        String suffix=infixToSuffix("a+b*c");
        System.out.println(suffix);
    }


    static int priority(char c) {
        return switch (c) {
            case '*', '/' -> 2;
            case '+', '-' -> 1;
            default -> throw new IllegalArgumentException("");
        };
    }

    static String infixToSuffix(String exp) {
        LinkedList<Character> stack = new LinkedList<>();
        StringBuilder sb = new StringBuilder(exp.length());

        char[] array = exp.toCharArray();
        for (char c : array) {
            switch (c) {
                case '*', '/', '+', '-' -> {
                    if (stack.isEmpty()) {
                        stack.push(c);
                    } else {
                        int p1 = priority(c);
                        int p2 = priority(stack.peek());
                        // 它的优先级比栈顶运算符高，入栈
                        if (p1 > p2) {
                            stack.push(c);
                            // 否则把栈里优先级大于等于他的都出栈，在入栈
                        } else {
                            while (!stack.isEmpty()) {
                                sb.append(stack.pop());
                            }
                            stack.push(c);
                        }
                    }
                }
                // 非运算符直接拼串
                default -> {
                    sb.append(c);
                }
            }
        }
        while (!stack.isEmpty()) {
            sb.append(stack.pop());
        }
        return sb.toString();
    }
}
